#include<iostream>
using namespace std;

struct ListNode {
    int data;
    ListNode* next;
};

void CreatList(ListNode* list, int nums[], int n) {
    ListNode* l1 = list;
    for (int i = 0; i < n; ++i) {
        ListNode* node = new ListNode;
        node->data = nums[i];
        node->next = nullptr;
        l1->next = node;
        l1 = l1->next;
    }
}

void PrintList(ListNode* list) {
    ListNode* l1 = list->next;
    while (l1) {
        cout << l1->data << " ";
        l1 = l1->next;
    }
    cout << endl;
}

// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* nextTemp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nextTemp;
    }
    return pre;
}

void reorderList(ListNode* list) {
    if (!list || !list->next || !list->next->next) return;

    ListNode* head = list;

    // 使用快慢指针找到中点
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 分割链表为前后两部分
    ListNode* secondHalf = slow->next;
    slow->next = nullptr;

    // 反转后半部分链表
    secondHalf = reverseList(secondHalf);

    // 合并两个链表
    ListNode* firstHalf = head->next;
    while (secondHalf) {
        ListNode* temp1 = firstHalf->next;
        ListNode* temp2 = secondHalf->next;

        firstHalf->next = secondHalf;
        secondHalf->next = temp1;

        firstHalf = temp1;
        secondHalf = temp2;
    }
}

int main() {
    ListNode* list = new ListNode();
    int nums[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = sizeof(nums) / sizeof(nums[0]);

    CreatList(list, nums, n);
    PrintList(list);

    reorderList(list);
    PrintList(list);

    return 0;
}